package com.fm.text.similarity;

import java.math.BigDecimal;

public class LevenshteinDistance {
	public static void main(String[] args) {
		String s1 = "china";
		String s2 = "id";
		System.out.println("matrix: " + matrix(s1, s2));
		System.out.println("similar: " + similarCalc(s1, s2));
	}

	private static int min(int one, int two, int three) {
		int min = one;
		if (two < min) min = two;
		if (three < min) min = three;
		return min;
	}

	public static int matrix(String s1, String s2) {
		int n = s1.length();
		int m = s2.length();
		int i;
		int j;

		int[][] matrix = new int[n + 1][m + 1];
		for (i = 0; i <= n; i++) {
			matrix[i][0] = i;
		}

		for (j = 0; j <= m; j++) {
			matrix[0][j] = j;
		}

		char c1;
		char c2;
		for (i = 1; i <= n; i++) {
			c1 = s1.charAt(i - 1);
			for (j = 1; j <= m; j++) {
				c2 = s2.charAt(j - 1);
				matrix[i][j] = min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + (c1 == c2 ? 0 : 1));
			}
		}

		return matrix[n][m];
	}

	public static BigDecimal similarCalc(String s1, String s2) {
		return new BigDecimal(1).subtract(
			new BigDecimal(matrix(s1, s2)).divide(
				new BigDecimal(Math.max(s1.length(), s2.length())),
				2,
				BigDecimal.ROUND_HALF_UP
			)
		);
	}
}
